package com.example.zzy.zzytest.algo.sort.bucket;

import com.example.zzy.zzytest.algo.sort.n2sort.InsertSort;

import java.util.Arrays;

/**
 * 桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，需要
 * 1在额外空间充足的情况下，尽量增大桶的数量
 * 2使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
 * 同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
 */
public class BucketSort {
    public static void main(String[] args) {
        int[] testArr = new int[]{29, 25, 3, 49, 9, 37, 21, 43};
        testArr = bucketSort(testArr, 5);
        for (int i : testArr) {
            System.out.print(i + " ");
        }
    }

    private static int[] bucketSort(int[] arr, int bucketSize) {
        if (arr.length <= 1) {
            return arr;
        }

        //找出数据边界
        int minVal = arr[0];
        int maxVal = arr[0];
        for (int num : arr) {
            if (num < minVal) {
                minVal = num;
            } else if (num > maxVal) {
                maxVal = num;
            }
        }

        //初始化桶
        int bucketCount = (int) Math.floor((maxVal - minVal) / bucketSize) + 1;
        int[][] buckets = new int[bucketCount][0];

        //放入数据
        for (int i = 0; i < arr.length; i++) {
            int index = (int) Math.floor((arr[i] - minVal) / bucketSize);
            buckets[index] = arrAppend(buckets[index], arr[i]);
        }

        //每个桶内排序
        int index = 0;
        for (int[] bucket : buckets) {
            if (bucket.length == 0) {
                continue;
            }
            InsertSort.sort(bucket);
            for (int value : bucket) {
                arr[index++] = value;

            }
        }
        return arr;
    }

    private static int[] arrAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }


}
